package main

import "fmt"

//给定一个可包含重复数字的序列，返回所有不重复的全排列。
//
//示例:
//输入: [1,1,2]
//输出:
//[
//  [1,1,2],
//  [1,2,1],
//  [2,1,1]
//]

func quicksort(nums []int, left, right int){
	i, j := left, right
	if i >= j{
		return
	}

	key := nums[i]
	for i < j{
		for ;i < j; j--{
			if nums[j] < key{
				break
			}
		}
		nums[i] = nums[j]
		for ;i<j; i++{
			if nums[i] > key{
				break
			}
		}
		nums[j] = nums[i]
	}
	nums[i] = key

	quicksort(nums, left, i)
	quicksort(nums, i+1, right)
}

func swap(nums []int, i, j int){
	temp := nums[i]
	nums[i] = nums[j]
	nums[j] = temp
}

func allsort(nums []int, pos int){
	if pos >= len(nums) - 1{
		fmt.Println(nums)
		return
	}

	for i := pos; i <= len(nums) - 1; i++{
		if i+1 < len(nums) && nums[i] == nums[i+1]{
			continue
		}

		swap(nums, i, pos)
		allsort(nums, pos+1)
		swap(nums, pos, i)
	}
}

func main(){
	allsort([]int{1, 1, 2}, 0)
}